"""
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 "0" 。


输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5
"""


class Solution:
    def largestNumber(self, cost, target: int) -> str:  # cost = [4,3,2,5,6,7,2,5,5]
        dp = [0] + [float('-inf')] * target
        for i in range(9, 0, -1):
            for j in range(1, target + 1):
                if j >= cost[i - 1]:
                    dp[j] = max(dp[j], (dp[j - cost[i - 1]] * 10) + i)
        return str(dp[target]) if dp[target] > 0 else '0'


obj = Solution()
print(obj.largestNumber([4, 3, 2, 5, 6, 7, 2, 5, 5], 9))
